package 力扣._00周赛._415周赛.问题3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution2 {

    class TrieNode {
        TrieNode[] children;
        boolean isEndOfWord;

        public TrieNode() {
            children = new TrieNode[26];  // 26 个字母
            isEndOfWord = false;
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        // 插入一个单词到前缀树中
        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }
            node.isEndOfWord = true;
        }

        // 返回从 target[start] 开始的所有前缀长度
        public List<Integer> searchPrefixes(String target, int start) {
            List<Integer> result = new ArrayList<>();
            TrieNode node = root;
            for (int i = start; i < target.length(); i++) {
                int index = target.charAt(i) - 'a';
                if (node.children[index] == null) {
                    break;  // 没有匹配到更多的前缀
                }
                node = node.children[index];
                if (node.isEndOfWord) {
                    result.add(i - start + 1);  // 找到了一个前缀，记录它的长度
                }
            }
            return result;
        }
    }

    public int minValidStrings(String[] words, String target) {
        int n = target.length();
        Trie trie = new Trie();

        // 构建前缀树
        for (String word : words) {
            trie.insert(word);
        }

        // 动态规划数组
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;  // 空字符串需要 0 个前缀

        // 动态规划
        for (int i = 0; i < n; i++) {
            if (dp[i] == Integer.MAX_VALUE) continue;  // 如果当前无法构造，跳过
            // 找到以 target[i] 开头的所有前缀
            List<Integer> prefixes = trie.searchPrefixes(target, i);
            for (int prefixLen : prefixes) {
                dp[i + prefixLen] = Math.min(dp[i + prefixLen], dp[i] + 1);
            }
        }

        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();

        // 示例 1
        String[] words1 = {"abc", "aaaaa", "bcdef"};
        String target1 = "aabcdabc";
        System.out.println(solution.minValidStrings(words1, target1));  // 输出 3

        // 示例 2
        String[] words2 = {"abababab", "ab"};
        String target2 = "ababaababa";
        System.out.println(solution.minValidStrings(words2, target2));  // 输出 2

        // 示例 3
        String[] words3 = {"abcdef"};
        String target3 = "xyz";
        System.out.println(solution.minValidStrings(words3, target3));  // 输出 -1
    }

}
